package other;

import java.util.ArrayList;

public class D230831 {
    // 旋转数组

    // 三次翻转
    // 1, 2, 3, 4, 5, 6
    // 2
    // 6, 5, 4, 3, 2, 1
    // 5, 6, 4, 3, 2, 1
    // 5, 6, 1, 2, 3, 4
    // 时间:O(n)
    // 空间:O(1)
    public int[] solve (int n, int m, int[] a) {

        // 处理 m
        m = m % n;

        int start = 0;
        int end = n - 1;
        // 第一次翻转
        reverse(a, start, end);
        // 第二次翻转
        end = m - 1;
        reverse(a, start, end);
        // 第三次翻转
        start = m;
        end = n - 1;
        reverse(a, start, end);
        return a;
    }
    // 翻转
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start++;
            end--;
        }
    }


    // 螺旋矩阵
    // 时间：O(mn)
    // 空间：O(1)
    public ArrayList<Integer> spiralOrder (int[][] matrix) {
        ArrayList<Integer> res = new ArrayList<>();
        if(matrix.length == 0) {
            return res;
        }
        // 左边界
        int left = 0;
        // 右边界
        int right = matrix[0].length - 1;
        // 上边界
        int up = 0;
        // 下边界
        int down = matrix.length - 1;

        while (left <= right && up <= down) {
            // 最上边一行，从左到右
            for (int i = left; i <= right; ++i) {
                res.add(matrix[up][i]);
            }
            // 上边界下移
            up++;
            if (up > down) break;

            // 最右边一列，从上到下
            for (int i = up; i <= down; ++i) {
                res.add(matrix[i][right]);
            }
            // 右边界左移
            right--;
            if (left > right) break;


            // 最下边一行, 从右到左
            for (int i = right; i >= left; --i) {
                res.add(matrix[down][i]);
            }
            // 下边界上移
            down--;
            if (up > down) break;


            // 最左边一列，从下到上
            for (int i = down; i >= up; --i) {
                res.add(matrix[i][left]);
            }
            left++;
            if (left > right) break;
        }
        return res;
    }
}
